import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: fzykd
 * Date: 2022-04-28
 * Time: 13:36
 */
class HashNode {
    public int key;
    public int val;
    public HashNode next;

    public HashNode(int key, int value){
        this.key = key;
        this.val = value;
    }

}

public class OpenHash {
    public HashNode[] array;
    public int usedSize;

    public final double DEFAULT_LOAD_FACTOR = 0.75;

    public OpenHash(){
        this.array = new HashNode[10];
    }


    public void put(int key,int val){//放入
        //1. 找到key所在位置
        int index = key % this.array.length;

        //2.遍历这个下标的链表 看看是不是有相同的key 有的话就要更新val值
        HashNode cur = array[index];
        while (cur != null){
            if (cur.key == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }

        //3.没有val这个元素，头插法
        HashNode hashNode = new HashNode(key,val);
        hashNode.next = array[index];
        array[index] = hashNode;
        this.usedSize++;

        // 4.负载因子的判断
        if (loadFactor() >= DEFAULT_LOAD_FACTOR){
            resize(); // 并不是简单的扩容 之前放的数据的位置也要发生改变 哈希函数也在改变
            // 都要进行重新哈希
        }

    }

    private void resize(){
        HashNode[] newArray = new HashNode[array.length*2];
        for (int i = 0; i < array.length; i++) {
            HashNode cur = array[i]; // 之前的下标 之下 还有链表 将链表的元素重新哈希 放入新的数组当中
            while (cur != null){
                int index = cur.key % newArray.length;//新的哈希函数 获取新的下标

                HashNode curNext = cur.next;//记录当前下标之下 链表的下一个节点

                cur.next = newArray[index];
                newArray[index] = cur;

                cur = curNext;
            }
        }
        array = newArray; // 后面的引用值赋给前面
    }

    public double loadFactor(){
        return 1.0*usedSize/array.length;
    }

    public int get(int key){ // 根据key 获取value值
        //1.找到key所在的位置
        int index = key % this.array.length;
        //2.遍历这个下标的链表
        HashNode cur = array[index];
        while (cur != null){
            if (cur.key == key){
                return cur.val;
            }
            cur = cur.next;

        }
        return -1;
    }

    public static void main(String[] args) {
        OpenHash openHash = new OpenHash();
        openHash.put(1,1);
        openHash.put(12,12);
        openHash.put(3,3);
        openHash.put(6,6);
        openHash.put(7,7);
        openHash.put(2,2);
        openHash.put(11,11);
        openHash.put(8,8);

        System.out.println(openHash.get(11));

    }
}
